package com.yangli.leecode.mashib.code;

/**
 * @Description
 * @Author liyang
 * @Date 2023/5/30 14:46
 */
public class Code_KMP {
    public static void main(String[] args){

    }

    //str1包含str2，求str2在str1的起始位置，并且算法复杂度为O（n）
    public static int kmp(String str1, String str2){
        if (str1 == null || str2 == null || str2.length() < 1 || str1.length() < str2.length()) {
            return -1;
        }
        int[] next = getNextArray(str2);
        int s1 = 0;
        int s2 = 0;
        while (s1 < str1.length() && s2 < str2.length()) {
            if (str1.charAt(s1) == str2.charAt(s2)) {
                s1++;
                s2++;
            } else if (next[s2] == -1) {
                s1++;
            } else {
                s2 = next[s2];
            }
        }
        return s2 == str2.length() ? s1 - s2 : -1;
    }


    //获取str2 前缀和后缀一样最大长度的辅助数组
    public static int[] getNextArray(String str2){
        if (str2.length() == 1) {
            return new int[]{-1};
        }
        int[] res = new int[str2.length()];
        res[0] = -1;
        res[1] = 0;
        int i = 2;
        int cn = 0;//表示要跟i-1位置比对的位置，一开始从0开始 表示比对位置也表示前后缀长度
        while (i < str2.length()) {
            if (str2.charAt(i - 1) == str2.charAt(cn)) {
                res[i++] = ++cn;
            } else if (cn > 0) {
                cn = res[cn];
            } else {
                res[i++] = 0;
            }
        }
        return res;
    }


}
